package com.ctrip.study.algorithm.pratice;

import org.junit.Test;

import junit.framework.TestCase;

/**
 * 最大连续子数组和.
 */
public class MaximumSubarray extends TestCase {

	@Test
	public void test() {
		int[] array = { 1, -2, 3, 10, -4, 7, 2, -5 };
		int sum = MaximumSubarray.maxSubArray(array);
		assertEquals(18, sum);
		int[] array2 = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
		int sum2 = MaximumSubarray.maxSubArray(array2);
		assertEquals(6, sum2);

	}

	private static int maxSubArray(int[] array) {
		return solution3(array);
	}
	
	
	/**
	 * 动态规划.
	 *
	 * @param array the array
	 * @return the int
	 */
	public static int solution3(int[] array) {
		int maxSum = array[0];
		int currSum = 0;
		for (int i = 0; i < array.length; i++) {
			if(currSum + array[i] > array[i]){
				currSum += array[i];
			}else{
				currSum = array[i];
			}
			maxSum = currSum > maxSum ? currSum : maxSum;
		}
		return maxSum;
	}
	
	

	/**
	 * 时间复杂度O(n).
	 *
	 * @param array the array
	 * @return the int
	 */
	public static int solution2(int[] array) {
		int maxSum = array[0];
		int currSum = 0;
		for (int j = 0; j < array.length; j++) {
			if (currSum >= 0) // 如果加上某个元素，sum>=0的话，就加
				currSum += array[j];
			else
				currSum = array[j]; // 如果加上某个元素，sum<0了，就不加
			if (currSum > maxSum)
				maxSum = currSum;
		}
		return maxSum;
	}

	/**
	 * 两层循环，效率不高.
	 *
	 * @param array
	 *            the array
	 * @return the int
	 */
	public static int solution1(int[] array) {
		int maxSum = 0;
		if (array == null) {
			return maxSum;
		}
		for (int i = 0; i < array.length; i++) {
			int sum = array[i];
			for (int j = i + 1; j < array.length; j++) {
				sum += array[j];
				maxSum = sum > maxSum ? sum : maxSum;
			}
		}
		return maxSum;
	}

}
